{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyArrayList:\n",
    "    # 默认初始容量\n",
    "    INIT_CAP = 1\n",
    "\n",
    "    def __init__(self, init_capacity=None):\n",
    "        self.data = [None] * (init_capacity if init_capacity is not None else self.__class__.INIT_CAP)\n",
    "        self.size = 0\n",
    "    \n",
    "    # 增\n",
    "    def add_last(self, e):\n",
    "        cap = len(self.data)\n",
    "        # 看 data 数组容量够不够\n",
    "        if self.size == cap:\n",
    "            self._resize(2 * cap)\n",
    "        # 在尾部插入元素\n",
    "        self.data[self.size] = e\n",
    "        self.size += 1\n",
    "\n",
    "    def add(self, index, e):\n",
    "        # 检查索引越界\n",
    "        self._check_position_index(index)\n",
    "\n",
    "        cap = len(self.data)\n",
    "        # 看 data 数组容量够不够\n",
    "        if self.size == cap:\n",
    "            self._resize(2 * cap)\n",
    "\n",
    "        # 搬移数据 data[index..] -> data[index+1..]\n",
    "        # 给新元素腾出位置\n",
    "        for i in range(self.size-1, index-1, -1):\n",
    "            self.data[i+1] = self.data[i]\n",
    "        \n",
    "        # 插入新元素\n",
    "        self.data[index] = e\n",
    "\n",
    "        self.size += 1\n",
    "\n",
    "    def add_first(self, e):\n",
    "        self.add(0, e)\n",
    "\n",
    "    # 删\n",
    "    def remove_last(self):\n",
    "        if self.size == 0:\n",
    "            raise NoSuchElementException\n",
    "        cap = len(self.data)\n",
    "        # 可以缩容，节约空间\n",
    "        if self.size == cap // 4:\n",
    "            self._resize(cap // 2)\n",
    "\n",
    "        deleted_val = self.data[self.size - 1]\n",
    "        # 删除最后一个元素\n",
    "        self.data[self.size - 1] = None\n",
    "        self.size -= 1\n",
    "\n",
    "        return deleted_val\n",
    "\n",
    "    def remove(self, index):\n",
    "        # 检查索引越界\n",
    "        self._check_element_index(index)\n",
    "\n",
    "        cap = len(self.data)\n",
    "        # 可以缩容，节约空间\n",
    "        if self.size == cap // 4:\n",
    "            self._resize(cap // 2)\n",
    "\n",
    "        deleted_val = self.data[index]\n",
    "\n",
    "        # 搬移数据 data[index+1..] -> data[index..]\n",
    "        for i in range(index + 1, self.size):\n",
    "            self.data[i - 1] = self.data[i]\n",
    "\n",
    "        self.data[self.size - 1] = None\n",
    "        self.size -= 1\n",
    "\n",
    "        return deleted_val\n",
    "\n",
    "    def remove_first(self):\n",
    "        return self.remove(0)\n",
    "\n",
    "    # 查\n",
    "    def get(self, index):\n",
    "        # 检查索引越界\n",
    "        self._check_element_index(index)\n",
    "\n",
    "        return self.data[index]\n",
    "\n",
    "    # 改\n",
    "    def set(self, index, element):\n",
    "        # 检查索引越界\n",
    "        self._check_element_index(index)\n",
    "        # 修改数据\n",
    "        old_val = self.data[index]\n",
    "        self.data[index] = element\n",
    "        return old_val\n",
    "\n",
    "    # 工具方法\n",
    "    def size(self):\n",
    "        return self.size\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.size == 0\n",
    "\n",
    "    # 将 data 的容量改为 newCap\n",
    "    def _resize(self, new_cap):\n",
    "        temp = [None] * new_cap\n",
    "        for i in range(self.size):\n",
    "            temp[i] = self.data[i]\n",
    "        self.data = temp\n",
    "\n",
    "    def _is_element_index(self, index):\n",
    "        return 0 <= index < self.size\n",
    "\n",
    "    def _is_position_index(self, index):\n",
    "        return 0 <= index <= self.size\n",
    "\n",
    "    def _check_element_index(self, index):\n",
    "        if not self._is_element_index(index):\n",
    "            raise IndexError(f\"Index: {index}, Size: {self.size}\")\n",
    "\n",
    "    def _check_position_index(self, index):\n",
    "        if not self._is_position_index(index):\n",
    "            raise IndexError(f\"Index: {index}, Size: {self.size}\")\n",
    "\n",
    "    def display(self):\n",
    "        print(f\"size = {self.size}, cap = {len(self.data)}\")\n",
    "        print(self.data)\n",
    "\n",
    "\n",
    "# Usage example\n",
    "if __name__ == \"__main__\":\n",
    "    arr = MyArrayList(init_capacity=3)\n",
    "\n",
    "    # 添加 5 个元素\n",
    "    for i in range(1, 6):\n",
    "        arr.add_last(i)\n",
    "\n",
    "    arr.remove(3)\n",
    "    arr.add(1, 9)\n",
    "    arr.add_first(100)\n",
    "    val = arr.remove_last()\n",
    "\n",
    "    # 100 1 9 2 3\n",
    "    for i in range(arr.size):\n",
    "        print(arr.get(i))"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
